package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-13 15:26
 */
public class DpBag {
    public static void main(String[] args) {
        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int bagSize = 4;
        MostWeightDpBag(weight, value, 4);

    }

    /**
     * 五部曲：1.dp[i][j] dp[i]是在0-i内存放东西的策略 j是背包容量为j,则dp[i][j]可以理解为在0-i的物品内和容量为j的背包所能存放的最大容量
     * 2.递推方程：dp[i][j]=math.max(dp[i-1][j],dp[i-1][j-w[i]])3.初始化当背包容量为0时，每一个i都是0，当物品为i时，每个背包能存放的最大价值为i
     * @param
     * @return
     */
    public static void MostWeightDpBag(int[]weight,int []value,int maxSize){
        //创建数组
        int[][]dp=new int[weight.length][maxSize+1];
        //初始化
        for(int i=weight[0];i<=maxSize;++i){
            dp[0][i]=value[0];
        }
        //循环
        //一层循环物品
        for(int i=1;i< weight.length;++i){
            //二层循环背包
            for(int j=1;j<=maxSize;++j){
                dp[i][j]=dp[i-1][j];
                if(weight[i]<=j){
                    dp[i][j]=Math.max(dp[i][j],dp[i][j-weight[i]]+value[i]);
                }
            }
        }
        for (int i = 0; i < weight.length; i++) {
            for (int j = 0; j <= maxSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }
    }
}
